package com.ry.day1129;

public class LC85 {


    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }


    static class Solution {
        /*
         * @param root: The root of the binary search tree.
         * @param node: insert this node into the binary search tree
         * @return: The root of the new binary search tree.
         */
        public TreeNode insertNode(TreeNode root, TreeNode node) {
            if (root == null) return node;
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                parent = cur;
                if (cur.val == node.val) {
                    cur.val = node.val;
                    return root;
                } else if (cur.val > node.val) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }

            if (parent.val > node.val) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            return root;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
85 · 在二叉查找树中插入节点
算法
简单
通过率
48%

题目
题解39
笔记
讨论99+
排名
记录
描述
给定一棵二叉查找树和一个新的树节点，将节点插入到树中。

你需要保证该树仍然是一棵二叉查找树。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


保证不会出现重复的值

样例
样例 1：

输入：

tree = {}
node= 1
输出：

{1}
解释：

在空树中插入一个点，应该插入为根节点。

样例 2：

输入：

tree = {2,1,4,#,#,3}
node = 6
输出：

{2,1,4,#,#,3,6}
解释：

85_1.png

挑战
能否不使用递归？

相关知识
学习《2024年10月北美大厂最新面试真题精讲》课程中的4.5Microsoft：最新面试精选003相关内容 ，了解更多相关知识！
标签
相关题目

87
删除二叉查找树的节点
困难

219
在排序链表中插入一个节点
简单

701
修剪二叉搜索树
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
27/3048
已开启智能提示
发起考试
15 分 00 秒
1234567891011121314151617181920212223





 */



